A Closed-Form Shave from Occam's Quantum Razor: Exact Results for Quantum Compression

摘要

The causal structure of a stochastic process can be more efficientlytransmitted via a quantum channel than a classical one, an advantage thatincreases with codeword length. While previously difficult to compute, weexpress the quantum advantage in closed form using spectral decomposition,leading to direct computation of the quantum communication cost at all encodinglengths, including infinite. This makes clear how finite-codeword compressionis controlled by the classical process' cryptic order and allows us to analyzestructure within the length-asymptotic regime of infinite-cryptic order (andinfinite Markov order) processes.